| 1. Identity statement | |
| Reference Type | Conference Paper (Conference Proceedings) |
| Site | sibgrapi.sid.inpe.br |
| Holder Code | ibi 8JMKD3MGPEW34M/46T9EHH |
| Identifier | 6qtX3pFwXQZG2LgkFdY/QGG9a |
| Repository | sid.inpe.br/sibgrapi@80/2007/07.09.17.59 |
| Last Update | 2007:07.09.17.59.09 (UTC) administrator |
| Metadata Repository | sid.inpe.br/sibgrapi@80/2007/07.09.17.59.10 |
| Metadata Last Update | 2022:06.14.00.13.27 (UTC) administrator |
| DOI | 10.1109/SIBGRAPI.2007.15 |
| Citation Key | CoutoSouzReze:2007:ExEfAl |
| Title | An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem  |
| Format | Printed, On-line. |
| Year | 2007 |
| Access Date | 2024, Apr. 29 |
| Number of Files | 1 |
| Size | 210 KiB |
| 2. Context | |
| Author | 1 Couto, Marcelo C. 2 Souza, Cid C. de 3 Rezende, Pedro J. de |
| Affiliation | 1 Institute of Computing, State University of Campinas, Campinas - Brazil 2 Institute of Computing, State University of Campinas, Campinas - Brazil 3 Institute of Computing, State University of Campinas, Campinas - Brazil |
| Editor | Falcão, Alexandre Xavier Lopes, Hélio Côrtes Vieira |
| Conference Name | Brazilian Symposium on Computer Graphics and Image Processing, 20 (SIBGRAPI) |
| Conference Location | Belo Horizonte, MG, Brazil |
| Date | 7-10 Oct. 2007 |
| Publisher | IEEE Computer Society |
| Publisher City | Los Alamitos |
| Book Title | Proceedings |
| Tertiary Type | Full Paper |
| History (UTC) | 2007-07-09 17:59:10 :: cid@ic.unicamp.br -> administrator :: 2007-08-02 21:17:16 :: administrator -> cid@ic.unicamp.br :: 2008-07-17 14:09:42 :: cid@ic.unicamp.br -> administrator :: 2009-08-13 20:38:18 :: administrator -> banon :: 2010-08-28 20:02:26 :: banon -> administrator :: 2022-06-14 00:13:27 :: administrator -> :: 2007 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Version Type | finaldraft |
| Keywords | Art Gallery Exact Solution Orthogonal Polygons Integer Programming Set Covering |
| Abstract | In this paper, we propose an exact algorithm to solve the Orthogonal Art Gallery problem in which guards can only be placed on the vertices of the polygon $ P$ representing the gallery. Our approach is based on a discretization of $ P$ into a finite set of points in its interior. The algorithm repeatedly solves an instance of the Set Cover problem obtaining a minimum set $ Z$ of vertices of $ P$ that can view all points in the current discretization. Whenever $ P$ is completely visible from $ Z$ , the algorithm halts; otherwise, the discretization is refined and another iteration takes place. We establish that the algorithm always converges to an optimal solution by presenting a worst case analysis of the number of iterations that could be effected. Even though these could theoretically reach $ O(n^4)$ , our computational experiments reveal that, in practice, they are linear in $ n$ and, for $ n\leq 200$ , they actually remain less than three in almost all instances. Furthermore, the low number of points in the initial discretization, $ O(n^2)$ , compared to the possible $ O(n^4)$ atomic visibility polygons, renders much shorter total execution times. Optimal solutions found for different classes of instances of polygons with up to 200 vertices are also described. |
| Arrangement 1 | urlib.net > SDLA > Fonds > SIBGRAPI 2007 > An Exact and... |
| Arrangement 2 | urlib.net > SDLA > Fonds > Full Index > An Exact and... |
| doc Directory Content | access |
| source Directory Content | there are no files |
| agreement Directory Content | there are no files |
| 4. Conditions of access and use | |
| data URL | http://urlib.net/ibi/6qtX3pFwXQZG2LgkFdY/QGG9a |
| zipped data URL | http://urlib.net/zip/6qtX3pFwXQZG2LgkFdY/QGG9a |
| Language | en |
| Target File | couto-ArtGallery.pdf |
| User Group | cid@ic.unicamp.br administrator |
| Visibility | shown |
| 5. Allied materials | |
| Next Higher Units | 8JMKD3MGPEW34M/46SF8Q5 8JMKD3MGPEW34M/4742MCS |
| Citing Item List | sid.inpe.br/sibgrapi/2022/05.14.00.14 3 |
| Host Collection | sid.inpe.br/banon/2001/03.30.15.38 |
| 6. Notes | |
| Empty Fields | archivingpolicy archivist area callnumber contenttype copyholder copyright creatorhistory descriptionlevel dissemination documentstage e-mailaddress edition electronicmailaddress group isbn issn label lineage mark mirrorrepository nextedition notes numberofvolumes orcid organization pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup readpermission resumeid rightsholder schedulinginformation secondarydate secondarykey secondarymark secondarytype serieseditor session shorttitle sponsor subject tertiarymark type url volume |